package leetcode_900;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *ShortestDistanceToACharacter_821 给定一个字符串和一个字符c 返回一个数组 里面这个下标元素离最近的c的距离
 *describe:用list映射c出现的index 用滑动窗口法解决 AC 44%
 *2018年10月29日 上午11:14:04
 */
public class ShortestDistanceToACharacter_821 {
	public int[] shortestToChar(String S, char C) {
        List<Integer> index=new ArrayList<Integer>();
        char []chars=S.toCharArray();
        for(int i=0;i<chars.length;++i) {
        	if(chars[i]==C)
        		index.add(i);
        }
        int left=index.get(0),right=left;
        int indexSize=0;
        int []res=new int[S.length()];
        for(int i=0;i<chars.length;++i) {
        	if(i>right) {
        		if(indexSize==index.size()-1) {//已经到了最右边界
        			res[i]=i-right;
        			continue;
        		}
        		else {
        			left=right;
        			right=index.get(++indexSize);
        		}
        	}
        	res[i]=Math.min(Math.abs(i-left), Math.abs(i-right));
        }
        return res;
    }
}	
